Write-Once Read-Many (WORM) media store data in addressable continuation lists or chains. Such lists or chains are linked lists of groups of addressable data-storing areas or disk sectors on WORM media. Generally, a given continuation chain is traversed to its end even when only a portion of the data stored in the chain are desired. A reason for this traversal is that the most recently recorded data, hence the correct data, are stored at a currently unknown location in the chain.
It is desired to cache WORM media operations for enhancing performance of the data storage system. It has been discovered that the usual cache page replacement algorithms when applied to cached WORM optical data storage systems result in poor and degraded performance, rather than the expected reduction in effective access time to data. An apparent reason for such poor performance by the usual page replacement systems is that the operation of the data storage system when operating with media using continuation chains is that medium accessing violates the principles of locality of references on which most page replacement algorithms are based. Locality of references merely means that if there is one read access to a given address, then the probability is that ensuing read accesses will be to addresses similar to or near the given address. Further, the continuation chains result in data being in long contiguous areas on each storage medium. All of these factors appear to cause the known FIFO (first in first out) and LRU (least recently used) to degrade system performance. It is desired to provide an enhanced page replacement method .and apparatus which departs from the LRU or FIFO schemes. Typically, when using the above-mentioned page replacement systems, a page being cast out turns out to be a next page requested by a using host processor. Such probability greatly reduces the efficiency of a cache connected to a medium using chaining as a data recording format. Accordingly, it is desired to provide a page replacement algorithm and apparatus which accommodates the format of continuation chains or linked list formatting of data on a storage medium.
Addressing the data can be achieved by two different procedures. A first procedure is by using a hash table of known design. A second procedure is to use a usual directory tree look up. It has been determined that optimum page replacement may be different for the two addressing or data area accessing procedures. It is desired to optimize page replacement based on the data accessing technique.